// 冒泡
// 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
// 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
// 针对所有的元素重复以上的步骤，除了最后一个。
// 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
let arr = [14,94,86,4,36,47,825,69,42,36,15,48,16,17]
function maopaoSort(arr){
    let index = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            index++
            if (arr[j] > arr[j+1]) {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
    console.log('---index----',index);
    return arr
}
// console.log(maopaoSort(arr));
// 改进1: 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
function maopaoSort2(arr){
    let i = arr.length - 1 //初始时,最后位置保持不变
    while (i > 0) {
        let pos = 0 //每趟开始时,无记录交换
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                pos = j;
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
        i = pos //为下一趟排序作准备
    }
    return arr
}
// console.log(maopaoSort2(arr));
// 改进2: 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) ,
//  从而使排序趟数几乎减少了一半。
// 普通冒泡排序每次循环只能减少一次的遍历，这个可以减少两次
function maopaoSort3(arr){
    let firstLen = 0;
    let lastLen = arr.length - 1;
    let temp;
    let index = 0;
    while (firstLen < lastLen) {
        for (let j = firstLen; j < lastLen ; ++j) { //找到最大值 从左往右
            if (arr[j] > arr[j+1]) {
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
            index++
        }
        lastLen--;
        for (let j = lastLen; j > firstLen ; --j) { //找到最小值 从右向左找
            if (arr[j] < arr[j-1]) {
                temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
            }
            index++
        }
        firstLen++;
    }
    return arr
}
// console.log(maopaoSort3(arr));
// 希尔排序 这个没看懂
// 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
// 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
// 按增量序列个数k，对序列进行k 趟排序；
// 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/5) {          //动态定义间隔序列
        gap =gap*5+1;
    }
   
    for (gap; gap > 0; gap = Math.floor(gap/5)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}
// console.log(shellSort(arr));
// 归并排序（Merge Sort）
// 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
// 算法简介
// 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
// 归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
// 若将两个有序表合并成一个有序表，称为2-路归并。
// 把长度为n的输入序列分成两个长度为n/2的子序列；
// 对这两个子序列分别采用归并排序；
// 将两个排序好的子序列合并成一个最终的排序序列。

// 我自己的理解
// 总体思想就是二分，分到最小一级，只有一个元素，然后再依次向上执行进行合并 
// 最佳情况：T(n) = O(n)
// 最差情况：T(n) = O(nlogn)  log代表对数 比如8的对数是3
// 平均情况：T(n) = O(nlogn)
function guibingSort(arr){ 
    let len = arr.length
    if (len < 2) {
        return arr //只有一个的话就直接返回
    }
    let middle = Math.floor(len / 2);
    let left   = arr.slice(0,middle);
    let right  = arr.slice(middle);
    return guibingMerge(guibingSort(left),guibingSort(right)) //当两个mergeSort执行return后就会去执行merge
}
function guibingMerge(left,right){
    let result = []
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }
    while (left.length) result.push(left.shift())
    while (right.length) result.push(right.shift())

    return result
}
// console.log(guibingSort(arr));

// 快速排序（Quick Sort）
// 算法简介
// 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
// 算法描述和实现
// 1.从数组中选择中间一项作为主元；
// 2.创建两个指针，左边一个指向数组的第一项，右边指向数组最后一项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素。
    // 然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程是的比主元小的值都排在了主元之前，而比主元大的值都排在了主元之后，这一步叫划分操作。
// 3.接着，算法对划分的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组以完全排序。
// 快速排序
const kuaisuSort = (function(){
    function compare(a,b){
        if (a === b) {
			return 0
		}
		return a < b ? -1 : 1
    }
    function swap(array,a,b){
        [array[a], array[b]] = [array[b], array[a]]
    }
    // 左边的都比他小，右边的都比他大 这个方法执行完就是这个元素的最终位置
    function partition(array,leftIndex,rightIndex){
        	// 用index取中间值而非splice
		const pivot = array[Math.floor((leftIndex + rightIndex) / 2)]
        while (leftIndex <= rightIndex) {
            while (array[leftIndex] < pivot) {
                leftIndex++
            }
            while (array[rightIndex] > pivot) {
                rightIndex--
            }
            if (leftIndex <= rightIndex) {
                swap(array,leftIndex,rightIndex);
                leftIndex++
                rightIndex--
            }
        }
        return leftIndex
    }
    // 最低的粒度是只有一个元素，当只有一个的话就退出当前递归，其实就相当于二叉树
    function quick(array,leftIndex,rightIndex){
        if (array.length > 0) {
          let index = partition(array,leftIndex,rightIndex)
            if (leftIndex < index - 1) { //左边下标必须小于右边 如果等于的话就只有一个元素了
                quick(array, leftIndex, index - 1)
            }
            if (index < rightIndex) {
                quick(array, index, rightIndex)
            }
        }
        return array;
    }
    return function kuaisuSort(array) {
		return quick(array, 0, array.length - 1)
	}
})()
let arr3 =[80,5,23,45,68,6,8,4,45,78,96,32,1,23]
console.log(kuaisuSort(arr3));
// 二分查找 要求是有序的
// 首先设两个指针，low和height，表示最低索引和最高索引
// 然后取中间位置索引middle，判断middle处的值是否与所要查找的数相同，相同则结束查找，middle处的值比所要查找的值小就把low设为middle+1，
    // 如果middle处的值比所要查找的值大就把height设为middle-1
// 然后再新区间继续查到，直到找到或者low>height找不到所要查找的值结束查找
// 非递归方式
function erfenSearch(arr,target){
    let min = 0;
    let max = arr.length-1
    while (min <= max) {
        let mid = Math.floor((max + min)/2)//注意这里是 max+min
        if(arr[mid] > target){
            max = mid - 1
        }else if(arr[mid] < target){
            min = mid + 1;
        }else{
            return mid
        }
    }
    return -1
}
// 递归方式
function erfenDiguiSearch(findTarget,left,right,arr){
    if(left > right){
        return -1
    }
    let mid = Math.floor((left+right)/2)
    if(arr[mid] > findTarget){
        return erfenDiguiSearch(findTarget,left,mid-1,arr)
    }else if(arr[mid] < findTarget){
        return erfenDiguiSearch(findTarget,mid+1,right,arr)
    }else{
        return mid
    }
}
let arr1 = [0, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 10, 11];
console.log(erfenDiguiSearch(6,0,arr1.length - 1,arr1));


// 一只青蛙一次可以跳上1级台阶,也可以跳上2级.求该青蛙跳上一个n级的台阶总共有多少种跳法
// 递归算法
// 缺点:太占空间,效率低下,计算到n时,总要依赖前一个n-1再算一遍 相当于指数级的增长，非常慢
function JumpFloor1(n) {
    console.log(1111111);
    if (n < 0) {
      return  0;
    } else  if (n == 0 || n == 1 || n == 2) {
      return  n;
    }
    return JumpFloor1(n - 1) + JumpFloor1(n - 2);
}
// 递归优化
// 记忆函数
let  memoizer = function(fn) {
    let  memo = [];
    return  function(n) {
        if(memo[n] === undefined) {
            memo[n] = fn(n)
        }
        return  memo[n]
    }
}
// 闭包缓存一个数组
let  fn = memoizer((n)=> {
    if(n === 0) return  0;
    if(n === 1 || n === 2) return  1;
    return  fn(n - 2) + fn(n - 1);
})
// console.log(fn(60));
// // 循环加解构赋值
let  fn2 = (n) => {
    let  n1 = 1,n2 = 1
    for(let  i=2;i<n;i++) {
        [n1,n2] = [n2,n1+n2]
    }
    return  n2
}
// console.log(fn2(60));
// 有十瓶药，其中有一瓶是假药，每一瓶都有100颗药，真药每一颗10G，假药每一颗9G，有一个小称，只称一次，如何找到假药
// 将10瓶药编好号，第1号取一粒，第2号取2粒，第三号取3粒....第10号取10粒，用天秤称得重量为x，用550-x得出的结果是那瓶假药

// 如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你从蓝色颜料桶里舀一杯，倒入红色颜料桶，再从红色颜料桶里舀一杯倒入蓝颜料桶。
// 两个桶中红蓝颜料的比例哪个更高？通过算术的方式来证明这一点
// 答案：假设桶各有10L颜料，满瓢为1L，那么第一次操作后。蓝桶有9L，100%纯度，红桶有11L，10/11纯度。
// 第二次操作后，蓝桶有10L，(9+（1/11）)/9+1=90.91%纯度。红桶有10L，10/11=90.91%，所以是一样多的。

// 复原IP地址（递归）JS
// 给定⼀个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
// 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间⽤ '.' 分隔。
// ⽰例:
// 输⼊: "25525511135"
// 输出: ["255.255.11.135", "255.255.111.35"]
var  restoreIpAddresses = function (str) {
    // 保存所有符合条件的IP地址
    let  res = [];
    // 递归函数
    let  search = (cur, sub) => {
        // 如果剩下的位数超过12位，就说明是非法的
        if (sub.length > 12) return
        // 边界条件，已经分完一种情况了，就将它push到res中
        if (cur.length === 4 && cur.join("") === str) {
            res.push(cur.join('.'))
            console.log('---完成一种情况---',cur.join('.'));
        } else {
            // 还没分完。正常处理情况
            // 如果剩下的数字不到3个了，就按照剩下的循环；否则按照三位循环
            for (let  i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) {
                    // 取出从0开始，i+1长度的子串，也就是1~len的子串
                    console.log('---len---',cur,len,sub);
                    tmp = sub.substr(0, i + 1)
                    // 对取出的子串验证是否合法
                    if (tmp - 256 < 0) { // 小于255合法
                        // 将这个合法的数字格式化（去掉前面的0），递归调用，进行下一次
                        // console.log('----a-----',cur);
                        let cur1 = cur.concat([tmp])
                        search(cur1, sub.substr(i + 1))
                    }
            }
        }
    }
    // 第一次调用
    search([], str)
    return  res
}
// console.log(restoreIpAddresses('101023'));
// 这个比较好理解一些  原理都是一样写法有些差别，排列组合，取一个/两个/三个 依次递归
let Solution  = function(str){
     // 保存所有符合条件的IP地址
     let  res = [];
     if (str.length > 12) return [];
    //pos 递归到字符串的第几个位置了
    //  
     let search = (pos,cur) =>{
        if (pos == str.length && cur.length == 4){
            /*合法的IP地址*/
            res.push(cur.join('.'))
            return;
        }
        if (pos > str.length || cur.length > 4) return;
        if (pos + 1 <= str.length) {
            search(pos+1,cur.concat(str.substr(pos, 1)))
        }
        if (pos + 2 <= str.length) {
            if (str[pos] != 0) {
                search(pos+2,cur.concat(str.substr(pos,2)))
            }
           
        }
        if (pos + 3 <= str.length) {
            let tmp = str.substr(pos, 3)
            if (tmp - 256 < 0 && str[pos] != 0) { // 小于255合法
                search(pos+3,cur.concat(str.substr(pos, 3)))
            }
        }
     }
    // 第一次调用
    search(0, [])
    return  res
}
// console.log(Solution('101023'));

// Nim 游戏桌子上有一堆石头。
// 你们轮流进行自己的回合，你作为先手。
// 每一回合，轮到的人拿掉 1 - 3 块石头。
// 拿掉最后一块石头的人就是获胜者。
// 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 

// 如果是4的整数倍的话你永远也不可能赢
var canWinNim = function(n) {
    return n % 4 === 0 ? false : true
};
// 灯泡开关
// 初始时有 n 个灯泡处于关闭状态。
// 对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
// 第 1 轮，每个灯泡切换一次开关。即，打开所有的灯泡。
// 第 2 轮，每两个灯泡切换一次开关。 即，每两个灯泡关闭一个。
// 第 3 轮，每三个灯泡切换一次开关。
// 第 i 轮，每 i 个灯泡切换一次开关。 而第 n 轮，你只切换最后一个灯泡的开关。
// 找出 n 轮后有多少个亮着的灯泡。

// 第18个灯泡会在1,2,3,6,9,18轮亮。
// 第36个灯泡会在1,2,3,4,6,9,12,18,36轮亮。

// 只有被操作奇数次的灯泡才会亮
// 只有完全平方数能够被操作奇数次：解释 对于一个数来说 存在因数m就必然存在x/m，所以只有完全平方数 才会有m*m 所以完全平方数一定有奇数个因子
// 所以这个题目就是找1到n中有多少个完全平方数 1*1,2*2,3*3 ... 根号n*根号n  就是一共有根号n个数
var bulbSwitch = function(n) {
    return Math.floor(Math.sqrt(n))
};

// 在LR字符串中交换相邻字符
// 在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。
// 现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。
var canTransform = function(start, end) {
    if (start.length !== end.length) return false; //先判断中长度
    let copyStart = start,copyEnd = end;
    if(copyStart.replace(/X/g,'') !== copyEnd.replace(/X/g,'')) { //在判断去掉了X之后剩下的长度是不是相等
        return false;    
    }
    let len = start.length, i = 0, j = 0;
    while (i < len && j < len) {
        while (i < len && start[i] == 'X') { //找到start中的第一个非X的字符串
            i++;
        }
        while (j < len && end[j] == 'X') {//找到end中的第一个非X的字符串
            j++;
        }
        if (start[i] !== end[j]) return  false;
        if ((start[i] == 'L' && i < j) || (end[j] == 'R' && i > j)) {
            return false
        }
        i++;
        j++;
        console.log(1111111);
    }
    return true;
};
// console.log(canTransform('RXR','XXR'));
// 'RXXLRXRXL'
// 'XRLXXRRLX'
// 'XRLXXRXRL'

// 移动石子直到连续
// 三枚石子放置在数轴上，位置分别为 a，b，c。
// 每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。
// 那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。
// 当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
// 要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答

// 输入：2 7 9 输出：[1,5]
// minimum_moves = 1 ， 2-> 8，7 8 9；
// maximum_moves = 5, 2->3->4->5->6，6->8，7 8 9
numMovesStones = function(a,b,c){
    let temp = [a,b,c];
    temp.sort((a,b)=>a-b) //排序
    let max = temp[2],mid = temp[1],min = temp[0];
    let str1 = 0
    if (max-mid == 1 && mid-min == 1 ) { //大小都是差1证明是连续的
        str1 = 0
    }else if(max-mid <= 2 || mid - min <= 2){ //大小相差一个或者两个直接移过去或者直接插入 也是一步
        str1 = 1
    }else{
        str1 = 2                              //移动多个距离然后插入 一次可以移动好几步
    }
    let str2 = (max-mid - 1) + (mid-min-1)   //一次移动一步
    return [str1,str2]
}

// 有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
// 剩下的乘客将会：
// 如果他们自己的座位还空着，就坐到自己的座位上，
// 当他们自己的座位被占用时，随机选择其他座位
// 第 n 位乘客坐在自己的座位上的概率是多少？

// 如果n=1那概率就是1
// 假设共有n个座位，令f(i)表示第一个人选择第i个人的座位时，第n个座位被其他人（1到n-1）占用的概率.
// 显然f(n)=1，即如果第一个人选择第n个座位，那么第n个座位必然是被其他占用了。
// f(n-1)=1/2，即如果1选择n-1，则2到n-2会对号入座，第n-1个人选择的时候有两种选择（1和n），选n的概率为1/2。
// f(n-2)=1/3+1/3f(n-1)=1/2，即如果第一个人选择第n-2个座位，那么第n-2个人有三种选择（1，n-1，n），每个都是1/3。如果选择n，那么概率为1/3；如果选择n-1座位，则第n-1个人做选择时，和第1个人选择n-1情况是一样的，即f(n-1)。
// 以此类推：
// f(n-3)=1/4+1/4f(n-1)+1/4f(n-2)=1/2
// ...
// ...
// ...
// f(2)=1/2
// f(1)=0
// 因此第n个座位被其他人占用的概率为1/n[f(2)+f(3)+...+f(n)]=1/2。
var nthPersonGetsNthSeat = function(n) {
    return n === 1 ? 1 : 0.5
};


// 所有蚂蚁掉下来前的最后一刻
// 有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
// 当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。
// 而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
// 给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻
// ### 解题思路
// 蚂蚁都一样，相撞即为穿过，所以只需要找到向右爬行的蚂蚁中起始位置距离终点最远的 和向左爬行的蚂蚁中起始位置距离板子起点最远的距离，比较大的那个，返回即可
var getLastMoment = function(n, left, right) {
    return Math.max(
      n - Math.min(...right), // 向右爬行距离最远的
      Math.max(...left) // 向左爬行距离最远的
    );
  };

